package hxy.bytecode.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 蛇形遍历二叉树 {
   public static List<List<Integer>>  zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(root, ans, 0);
        return ans;
    }

    private static void  helper(TreeNode node, List<List<Integer>> ans, int level) {
        if (node == null) return;
        if (ans.size() <= level) {
            List<Integer> newLevel = new LinkedList<>();
            ans.add(newLevel);
        }
        List<Integer> collection = ans.get(level);
        if (level % 2 == 0) {
            collection.add(node.val);
        } else {
            collection.add(0, node.val);
        }
        helper(node.left, ans, level + 1);
        helper(node.right, ans, level + 1);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode9 = new TreeNode(9);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;
        treeNode3.right=treeNode7;
        treeNode4.left=treeNode8;
        treeNode4.right=treeNode9;



        List<List<Integer>> lists = zigzagLevelOrder(treeNode1);
        for (List<Integer> list:lists){
            for (Integer integer:list){
                System.out.print(integer+"\t");
            }
            System.out.println();
        }

    }
}
//————————————————
//版权声明：本文为CSDN博主「CG国斌」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
//原文链接：https://blog.csdn.net/qq_35246620/java/article/details/106154953